/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 用单调不增栈
 * 遇到更大的就出栈，每出一个计算一个所能接的雨水（宽度乘以高度只之差）
 * 为什么不会漏算？因为乘以了宽度
 * 为什么乘以宽度不会多算？因为每出栈一次，计算完后可以看作当前柱子填平了高度
 */
var trap = function (height) {
  const stack = []
  let ans = 0
  for(let i = 0; i < height.length; i++) {
    while(stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      let topInx = stack.pop()
      // 栈顶柱子前面没有墙，直接跳出
      if(stack.length === 0) break
      let wallInx = stack[stack.length - 1]
      let topHeight = Math.min(height[i], height[wallInx]) - height[topInx]
      ans += topHeight * (i - wallInx - 1)
    }
    stack.push(i)
  }
  return ans
};
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));